
package uk.ac.cam.cl.oscar.edgefinder;

import java.util.*;
import java.lang.*;
import uk.ac.cam.cl.oscar.*;

/** A neat little class, that given a bunch of points (sensibly 4 points) will
	work which should be which edge of the rectangle they create */
public class CornerSorter {

	private Vector<NormalisedPoint> points;
	private Vector<NormalisedPoint> hull; /* Order: top-left, top right, bot right, bot left */
	boolean solved; /* A 'dirty' flag of wether we need to re-solve */

	public CornerSorter () {
		points = new Vector<NormalisedPoint> (4);
		hull = new Vector<NormalisedPoint> (4);
		solved = false;
	}
	
	public void add (NormalisedPoint p) {
		points.add(p);
		solved = false;
	}
	
	public int pointCount () {
		return points.size();
	}
	
	private NormalisedPoint findClosest (NormalisedPoint p) throws Exception {
		NormalisedPoint best = null;
		double bestDist = -1;
		
		if (points.size() == 0) {
			throw new Exception ("Trying to anaylse an empty point set!");
		}
		
		for (NormalisedPoint i : points) {
			double d = NormalisedPoint.normalDistance (i, p);
			if (d < bestDist || bestDist < 0) {
				best = i;
				bestDist = d;
			}
		}
		
		return best;
	}
	
	/* For determining the which point is 'more clockwise' of the other etc */
	private double cross (NormalisedPoint o, NormalisedPoint a, NormalisedPoint b) {
		double m = NormalisedPoint.normalDistance(o,a) * NormalisedPoint.normalDistance(o,b);
		if (m < 0.1) m = 0.1;
		return ( (a.x()-o.x()) * (b.y()-o.y()) - (b.x()-o.x()) * (a.y()-o.y())) / m;
   	}
	
	/* Part of Jarvis March */
	private NormalisedPoint findNextPoint (NormalisedPoint point)
	{
            NormalisedPoint v1 = new NormalisedPoint(point.x()+1, point.y());
            NormalisedPoint minPoint = point;

            Random r = new Random();
            while (point.equals(minPoint)) {
                minPoint = points.elementAt((int)Math.floor(r.nextDouble() * points.size()));
            }
            double minCS = cross(point, v1, minPoint);

            double c;
            System.out.println("Cross values: ");
            for (NormalisedPoint p : points) {
                if (!p.equals(point)) {
                    c = cross(point, v1, p);
                    System.out.printf(c + " " + p.toString() + "\n");
                    if ((c > 0) && (c < minCS)) {
                        minPoint = p;
                        minCS = c;
                    }
                }
            }
            return minPoint;


		/* What needs filled in here, in python. translating should be quite easy
		 	(it's just JARVIS MARCH )
		
		 v1 = Pt (pt.x + 1, pt.y) 

        self.points.sort(key=lambda a:cross(pt, v1, a))
        
        minpt = pt
        while pt == minpt:
            minpt = self.points[int(math.floor(random.random()*len(self.points)))]
        mincs = cross (pt, v1, minpt)

        print "cross values:"
        for i in self.points:
            if i != pt:
                c = cross (pt, v1, i)
                print str(c) + " " + str(i)
                if c > 0 and c < mincs:
                    minpt = i
                    mincs = c
        
        return minpt
        */
	}
	
	/* Perform a Jarvis march to find the convex hull that the points of the
		rectangle make, such that we have a plausable order!
		*/
	private void solve () {
		
		if (!solved) {
		
			hull.clear();
            NormalisedPoint minPoint = points.elementAt(0);
            for(NormalisedPoint p : points) {
                if ((p.y() <= minPoint.y()) || ((p.y() == minPoint.y()) && (p.x() < minPoint.x()))) {
                    minPoint = p;
                }
            }

            NormalisedPoint maxPoint = points.elementAt(0);
            for(NormalisedPoint p : points) {
                if ((p.y() >= maxPoint.y()) || ((p.y() == maxPoint.y()) && (p.x() > maxPoint.x()))) {
                    maxPoint = p;
                }
            }

            Vector<NormalisedPoint> solution = new Vector<NormalisedPoint>();
            solution.addElement(minPoint);

            NormalisedPoint p = new NormalisedPoint(0, 0);
            int count = 0;

            while ((!p.equals(minPoint)) && (count < 10)) {
                p = findNextPoint(solution.elementAt(count));
                solution.addElement(p);
                count++;
            } 
			/* 	Once this method is complete, just get the other public methods
				always call solve, and have them find the appropriate point
				in the hull. Then this will be better and stronger!
				
				
				what needs put here (i.e. JARVIS MARCH )
			
			assert (len(self.points) > 2)
			
			minpt = self.points[0]
			for i in self.points:
				if i.y <= minpt.y or (i.y == minpt.y and i.x < minpt.x):
					minpt = i        
	
			maxpt = self.points[0]
			for i in self.points:
				if i.y >= maxpt.y or (i.y == maxpt.y and i.x > maxpt.x):
					maxpt = i
	
			sol = [minpt]
			# March one
			pt = Pt(0,0)
			count = 0
			
			while (pt != minpt) and count < 10:
				pt = self.findNextPt (sol[-1])
				sol.append (pt)
				count = count + 1
			
		   */
			
			solved = true;
		}
	}
	
	public NormalisedPoint getTopLeft () throws Exception  {
		return findClosest (new NormalisedPoint(-1,-1));
	}
	
	public NormalisedPoint getTopRight () throws Exception  {
		return findClosest (new NormalisedPoint(1,-1));
	}
	
	public NormalisedPoint getBottomLeft () throws Exception  {
		return findClosest (new NormalisedPoint(-1,1));
	}
	
	public NormalisedPoint getBottomRight () throws Exception  {
		return findClosest (new NormalisedPoint(1,1));
	}

}
